package LinkedList;

/**
 *  题目 ：重排链表
 *
 *  给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 * 请将其重新排列后变为：
 * L0→Ln→L1→Ln-1→L2→Ln-2→ …
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 */
public class ResortedLinkList {
    /**
     *  思路 ：
     *  （1）寻找到链表的中心结点（由于链表只能从头进行遍历，所以通过快慢指针进行遍历，可以更快地定位中间节点）
     *  （2）将后半段的链表进行反转（三指针方法）  ===》 链表二
     *  （3）将链表一和二重新组成一条新的链表
     */
    public void reorderList(ListNode head) {
        ListNode dummy = new ListNode(0); // 哨兵结点
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        while(fast != null && fast.next != null){
            fast = fast.next;
            slow = slow.next;
            if(fast.next != null){
                fast = fast.next;
            }
        }
        // 后一段链表的起始节点
        ListNode afterList = slow.next;
        // 此处同时需要将前一段链表和后一段链表进行截断，即使得前一段链表的最后一个节点指向null值
        slow.next = null;
        resortedList(head,reverseList(afterList),dummy); // 此处想将第一条链表进行重构
    }

    private void resortedList(ListNode node1, ListNode node2,ListNode dummy) {
        ListNode head = dummy;
        // 由于在重建List1的while循环中，
        // dummy只是在其中进行改变，所以需要定义一个成员变量来记录其变化
        while(node1 != null && node2 != null){
            // 由于是对于List1链表进行重构，即需要保存List1中next指向的下一个结点
            ListNode temp = node1.next;
            head.next = node1;
            node1.next = node2;
            head = node2;
            // 将需要合并的两条链表，进行双指针的后移
            node1 = temp;
            node2 = node2.next;
        }
        if(node1 != null){
            head.next = node1;
        }
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode now = head;
        while(now != null){
            ListNode next = now.next;
            now.next = prev;
            prev = now;
            now = next;
        }
        return prev;
    }

}
